/**
 * @param {number[][]} grid
 * @return {number}
 */
var minPathSum = function (grid) {
  const m = grid.length;
  const n = grid[0].length;
  const map = new Array(m).fill(0).map(() => new Array(n).fill(0));
  map[0][0] = grid[0][0];
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      if (i == 0 && j !== 0) {
        map[i][j] = grid[i][j] + map[i][j - 1];
      } else if (i !== 0 && j === 0) {
        map[i][j] = grid[i][j] + map[i - 1][j];
      } else if (i !== 0 && j !== 0) {
        map[i][j] = grid[i][j] + Math.min(map[i - 1][j], map[i][j - 1]);
      }
    }
  }

  return map[m - 1][n - 1];
};

/**
 * @param {number[][]} grid
 * @return {number}
 */
// 这个 ai 的回答好像比较好
/* 
方法思路
初始化 DP 数组：创建一个与输入网格大小相同的二维数组dp。
处理边界条件：
dp[0][0]即为起点的值。
第一行的每个位置只能从左边的位置向右移动到达，因此dp[0][j] = dp[0][j-1] + grid[0][j]。
第一列的每个位置只能从上边的位置向下移动到达，因此dp[i][0] = dp[i-1][0] + grid[i][0]。
状态转移方程：对于其他位置(i, j)，可以从上方(i-1, j)或左方(i, j-1)移动到达，取两者中的较小值加上当前位置的值，即dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]。
结果：右下角的dp[m-1][n-1]即为所求的最小路径和。
*/
var minPathSum = function (grid) {
  const m = grid.length;
  const n = grid[0].length;
  const dp = Array.from({ length: m }, () => Array(n).fill(0));

  dp[0][0] = grid[0][0];

  // 初始化第一行
  for (let j = 1; j < n; j++) {
    dp[0][j] = dp[0][j - 1] + grid[0][j];
  }

  // 初始化第一列
  for (let i = 1; i < m; i++) {
    dp[i][0] = dp[i - 1][0] + grid[i][0];
  }

  // 填充剩余的dp数组
  for (let i = 1; i < m; i++) {
    for (let j = 1; j < n; j++) {
      dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
    }
  }

  return dp[m - 1][n - 1];
};